# -*- coding:utf-8 -*-
# @File       :   在线选举.py
# @Author     :   LINING
# @Time       :   2024/3/13 14:41
# @Description :
"""
https://leetcode-cn.com/problems/online-election/
给你两个整数数组 persons 和 times 。在选举中，第 i 张票是在时刻为 times[i] 时投给候选人 persons[i] 的。

对于发生在时刻 t 的每个查询，需要找出在 t 时刻在选举中领先的候选人的编号。

在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。

实现 TopVotedCandidate 类：

TopVotedCandidate(int[] persons, int[] times) 使用 persons 和 times 数组初始化对象。
int q(int t) 根据前面描述的规则，返回在时刻 t 在选举中领先的候选人的编号。

示例：

输入：
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
输出：
[null, 0, 1, 1, 0, 0, 1]

解释：
TopVotedCandidate topVotedCandidate = new TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]);
topVotedCandidate.q(3); // 返回 0 ，在时刻 3 ，票数分布为 [0] ，编号为 0 的候选人领先。
topVotedCandidate.q(12); // 返回 1 ，在时刻 12 ，票数分布为 [0,1,1] ，编号为 1 的候选人领先。
topVotedCandidate.q(25); // 返回 1 ，在时刻 25 ，票数分布为 [0,1,1,0,0,1] ，编号为 1 的候选人领先。（在平局的情况下，1 是最近获得投票的候选人）。
topVotedCandidate.q(15); // 返回 0
topVotedCandidate.q(24); // 返回 0
topVotedCandidate.q(8); // 返回 1
"""
# 0分钟投票给0，5分钟公投票给1，10分钟投票给1，15分钟投票给0
# 第i分钟，投票人数为x，哪个人达到了
ticket = [0, 1, 1, 0, 0, 1, 0]
times = [0, 5, 10, 15, 20, 25, 30]


def get_tickets(tickets, times):
    """
    tickets：投票票数组
    times：时间数组
    return: 按照时间排序的胜利者
    """
    # 记录票数
    result = {}
    # 当前时间点的胜利者
    max_person = []
    for i in range(len(times)):
        if tickets[i] not in result:
            result[tickets[i]] = 1
        else:
            result[tickets[i]] = result[tickets[i]]+1
        result_max = sorted(result.items(), key=lambda x: x[1])[-1]
        # 当前最大票数的人
        current_max = result_max[0]
        # 当前票数
        current_ticket = result_max[1]
        if current_ticket == result[tickets[i]]:
            max_person.append(tickets[i])
        else:
            max_person.append(current_max)
    return max_person


def get_winner(minute,tickets,times):
    """
        minute:要查询的时间
        tickets：投票票数组
        times：时间数组
        return: 按照时间排序的胜利者
        """
    left = 0
    right = len(times)
    max_person = get_tickets(tickets, times)
    time_winner = dict(zip(times, max_person))
    while left < right:
        # 最后一个小于等于minute的时间点
        mid = int((left+right+1)/2)
        if minute < times[mid]:
            right = mid-1
        else:
            left = mid
    print(time_winner[times[right]])


get_winner(25,ticket, times)


